// 二分法：[]
class Solution 
{
public:
    int search(vector<int>& nums, int target)
    {
        int l=0, r=nums.size()-1;
        while (l<=r)
        {
            int mid=l+(r-l)/2;
            if(nums[mid]>target)
                r = mid-1;
            else if(nums[mid]<target)
                l= mid+1;
            else
                return mid;
        }
        return -1;
    }
};

// 二分法：[)
class Solution
{
public:
    int search(vector<int>& nums, int target)
    {
        int l=0, r=nums.size();
        while (l<r)
        {
            int mid=l+(r-l)/2;
            if(nums[mid]>target)
                r=mid;
            else if(nums[mid]<target)
                l=mid+1;
            else    
                return mid;
        }
        return -1;
    }
};

// 移除元素
class Solution
{
public:
    int remove(vector<int>& nums, int val)
    {
        int slow=0;
        for (int fast = 0; fast < nums.size(); fast++)
        {
            if (val!=nums[fast])
            {
                nums[slow++]=nums[fast];
            }
        }
        return slow;
    }
};

// 有序数组的平方
class Solution
{
public:
    vector<int> sortedSqure(vector<int>& A)
    {
        int k=A.size()-1;
        vector<int> res(A.size(), 0);
        for (int i=0, j=A.size()-1; i <= j;)
        {
            if(A[i]*A[i]<A[j]*A[j])
            {
                res[k--]=A[j]*A[j];
                j--;
            }
            else
            {
                res[k--]=A[i][i];
                i++;
            }
        }
        return res;
    }

};

// 长度最小的子数组
class Solution{
public:
    int minSubArrayLen(int s, vector<int>& nums){
        int resLen=INT32_MAX;
        int sum=0;
        int i=0;
        int subLen=0;
        for(int j=0;j<nums.size();j++){
            sum+=nums[j];
            while(sum>=s){
                subLen=j-i+1;
                resLen=resLen<subLen?resLen:subLen;
                sum-=nums[i++];
            }
        }
        return resLen<INT32_MAX?resLen:0;
    }
};

// 螺旋矩阵II
class Solution{
public:
    vector<vector<int>> generateMatrix(int n){
        vector<vector<int>> res(n, vector<int>(n, 0));
        int startx=0, starty=0;
        int loop=n/2;
        int mid=n/2;
        int count=1;
        int offset=1;
        int i,j;
        while(loop--){
            i=startx;
            j=starty;
            for(j;j<n-offset;j++;)
                res[i][j]=count++;
            for(i;i<n-offset;i++;)
                res[i][j]=count++;
            for(;j>starty;j--;)
                res[i][j]=count++;
            for(;i>startx;i--;)
                res[i][j]=count++;
            // second circle
            startx++;
            starty++;
            offset+=1;
        }
        if(n%2)
            res[mid][mid]=count;
        return res;
    }
}
// 